/* 
 * Sort Colors
 */

#include "../func.h"

void sortColors1(vector<int> &A)
{
    int counts[3] = {0};

    for (int i = 0; i < A.size(); ++i)
        counts[A[i]]++;

    for (int i = 0, index = 0; i < 3; ++i)
        for (int j = 0; j < counts[i]; ++j)
            A[index++] = i;
}

void sortColors2(vector<int> &A) {
    int red = 0, blue = A.size() - 1;

    for (int i = 0; i < blue + 1;) {
        if (A[i] == 0)
            swap(A[i++], A[red++]);
        else if (A[i] == 2)
            swap(A[i], A[blue--]);
        else
            i++;
    }
}